% Ejercicio "Tres en raya"
\subsection*{\fbox{\theejercicio} - Tres en raya}

Consideremos el siguiente juego basado en el de las ``3 en raya'':

\begin{itemize}
\item Existen dos jugadores, uno juega con fichas blancas, y el otro con negras. Existe un tablero de $M \times M$ celdas. Normalmente $M$ es 3, aunque para nuestro juego $M$ puede ser cualquier n\'umero mayor o igual que 3. A ``$M$'' la llamaremos ``dimensi\'on'' del juego.

\item Cada jugador dispone de $M$ fichas de su color. Los turnos se van alternando entre los dos jugadores, y en cada turno, un jugador pone una ficha en alguna de las celdas vac\'{\i}as.

\item Gana el jugador que antes consiga tener sus $M$ fichas en ``raya''. Una vez situadas todas las fichas, se puede jugar otra partida. Lo habitual es que cada jugada acabe en empate, pues ninguno de los jugadores consiga poner las fichas en l\'{\i}nea.
\end{itemize}

Para este juego, consideramos el siguiente lenguaje con dos instrucciones:

\begin{verbatim}
define dimension M  Para definir la dimension del juego.
situaX (n1, n2)     Para situar una ficha de color X (X igual a "B", o
                    "N", blanca o negra respectivamente, tambien valen
                    las minusculas, "b" o "n"), y (n1, n2) especifica
                    una celda del tablero. n1 y n2 pueden tomar valores
                    de 0 a M-1.
\end{verbatim}

Como ejemplos de este lenguaje, y el contenido del tablero una vez ejecutadas las instrucciones correspondientes:

\smallskip

\begin{minipage}{4cm}
\begin{tabular}{|c|c|c|} \hline
        &         & {\tt B} \\ \hline
{\tt B} & {\tt N} & {\tt N} \\ \hline
{\tt N} &         & {\tt B} \\ \hline
\end{tabular}

\medskip

\begin{tabular}{|c|c|c|c|} \hline
        & {\tt N} & {\tt N} & {\tt N} \\ \hline
{\tt B} & {\tt B} & {\tt B} & {\tt B} \\ \hline
        &         & {\tt N} &         \\ \hline
        &         &         &         \\ \hline
\end{tabular}
\end{minipage}
\ \ \hfil \begin{minipage}{9cm}
\begin{tabular}{|l|} \hline
{\tt define dimension 3}                     \\
{\tt situaB (0,2) situaN (1,1) situaB (2,2)} \\
{\tt situaN (1,2) situaB (1,0) situaN (2,0)} \\ \hline
\end{tabular}

\medskip

\begin{tabular}{|l|} \hline
{\tt define dimension 4}        \\
{\tt situaN (0,2) situab (1,1)} \\
{\tt situan (2,2) situab (1,2)} \\
{\tt situan (0,1) situaB (1,0)} \\
{\tt situan (0,3) situab (1,3)} \\ \hline
\end{tabular}
\end{minipage}

\smallskip

Ante el primer ejemplo, el programa debe responder ``empate'', y ante el segundo, debe responder ``las blancas ganan''.

\smallskip

Construir un programa LEX/YACC para este lenguaje, t\'engase en cuenta lo siguiente:

\begin{itemize}
\item La alternancia entre {\tt situaN} y {\tt situaB} debe controlarse sint\'acticamente.
\item Sem\'anticamente deben controlarse los errores: la dimensi\'on no puede ser menor que 3, no se puede situar una ficha en una celda ya ocupada, no se puede indicar una celda fuera de las dimensiones del tablero, no se pueden situar m\'as fichas de las $2*M$ disponibles.
\item El programa recibe las instrucciones de una partida, y responde seg\'un el resultado: ``empate'', o ``ganan las ...''. El programa debe aceptar varias partidas (por ejemplo, las dos partidas anteriores seguidas).
\item Se pueden utilizar las siguientes variables, funciones y definiciones:

\begin{verbatim}
char **tabla; /* Contendra el tablero */
int dimension; /* Valor de la dimension en cada partida*/
#define BLANCA 1 /* Codigos para manejar el color de la ficha */
#define NEGRA 2
#define VACIO 0
%union {
   int val; /* Valor para los numeros */
   int contador; /* Para controlar las fichas del tablero */
   struct {int x; int y;} celda; /* Posicion de la celda */
}
void initabla(int dimension); /* Para inicializar el tablero 
                                 en cada partida */
int comprobarRaya(); /* Una vez que se han puesto 2*M fichas o
2*M-1 fichas, hay que comprobar si hay ya raya de algun color.
Esta funcion hace esta comprobacion, y devuelve BLANCA o NEGRA,
si existe, o bien VACIO, si no existe raya de ninguno de los dos
colores
*/
\end{verbatim}
\end{itemize}

% Solución del ejercicio
\subsubsection*{SOLUCI\'ON}

